Giải thuật Euclid là một trong những thuật toán lâu đời nhất được sử dụng rộng rãi.[25] Nó xuất hiện trong bộ Cơ sở của Euclid (khoảng 300 TCN), đặc biệt là ở cuốn 7 (mệnh đề 1–2) và cuốn 10 (mệnh đề 2–3). Trong cuốn 7, thuật toán được phát biểu cho số nguyên, còn trong cuốn 10, nó được phát biểu cho độ dài của đoạn thẳng. (Ngày nay, ta có thể nói thuật toán được phát biểu cho số thực. Nhưng độ dài, diện tích và thể tích, vốn được đo bằng số thực trong thời kỳ hiện đại, lại không có cùng đơn vị đo và cũng không có đơn vị đo tự nhiên nào cho chúng; người xưa lúc bấy giờ vẫn chưa hiểu rõ khái niệm số thực.) Thuật toán trong cuốn 10 mang tính hình học: ƯCLN của hai độ dài a và b là độ dài lớn nhất g có thể làm đơn vị đo chung cho a và b; nói cách khác, độ dài a và b là bội số của độ dài g.

Có lẽ giải thuật trên không phải do Euclid trực tiếp tìm ra (ông là người đã sưu tầm các công trình của các nhà toán học khác và tổng hợp lại trong bộ Cơ sở).[26][27] Nhà toán học và sử học B. L. van der Waerden cho rằng cuốn 7 xuất phát từ một cuốn sách giáo khoa về lý thuyết số được viết bởi các nhà toán học trong trường của Pythagoras.[28] Giải thuật có thể đã được biết bởi Eudoxus của Cnidus (khoảng 375 TCN),[25][29] hoặc thậm chí có thể đã có từ trước thời của ông,[30][31] dựa trên thuật ngữ ἀνθυφαίρεσις (anthyphairesis, phép trừ nghịch đảo) trong một số công trình của Euclid và Aristotle.[32]

Nhiều thế kỷ sau, giải thuật Euclid được tìm ra một cách độc lập tại Ấn Độ và Trung Quốc,[33] chủ yếu để giải phương trình Diophantine vốn nảy sinh trong thiên văn học và làm lịch chính xác. Vào cuối thế kỷ 5, nhà toán học và thiên văn người Ấn Độ Aryabhata đã gọi giải thuật là một "máy nghiền",[34] có thể là vì tính hiệu quả của nó trong việc giải phương trình Diophantine.[35] Mặc dù một trường hợp đặc biệt của định lý số dư Trung Quốc đã được mô tả trong cuốn Sunzi Suanjing,[36] lời giải tổng quát được Tần Cửu Thiều xuất bản trong cuốn Shushu Jiuzhang (數書九章, Giáo trình Toán học trong 9 chương) năm 1247.[37] Giải thuật Euclid lần đầu tiên được mô tả và truyền bá tại châu Âu trong cuốn Problèmes plaisants et délectables (ấn bản thứ hai) của Bachet năm 1624.[34] Tại châu Âu, nó cũng được sử dụng để giải phương trình Diophantine và lập liên phân số. Giải thuật Euclid mở rộng được cho là do Roger Cotes tìm ra và được Nicholas Saunderson xuất bản như là một cách để tính nhanh liên phân số.[38][39]

Đến thế kỷ 19, giải thuật Euclid đã dẫn đến sự ra đời và phát triển của các hệ thống số học mới, chẳng hạn như số nguyên Gauss và số nguyên Eisenstein. Năm 1815, Carl Gauss sử dụng giải thuật này để chứng minh tính duy nhất của sự phân tích các số nguyên Gauss, mặc dù công trình của ông chỉ được xuất bản lần đầu năm 1832.[40] Gauss trước đó cũng từng nhắc đến giải thuật trong cuốn Disquisitiones Arithmeticae (xuất bản 1801) liên quan đến liên phân số.[33] Peter Gustav Lejeune Dirichlet có thể là người đầu tiên mô tả giải thuật như là một cơ sở của phần lớn lý thuyết số.[41] Lejeune Dirichlet nhận thấy rằng nhiều hệ quả của lý thuyết số là đúng với bất kỳ hệ thống số học nào mà giải thuật Euclid có thể áp dụng được.[42] Những bài giảng của Dirichlet về lý thuyết số đã được biên tập và mở rộng bởi Richard Dedekind, người đã ứng dụng giải thuật để nghiên cứu số đại số nguyên, một dạng số tổng quát mới. Chẳng hạn, Dedekind là người đầu tiên chứng minh được định lý Fermat về tổng của hai số chính phương qua sự phân tích duy nhất số nguyên Gauss.[43] Ông cũng định nghĩa khái niệm miền Euclid, một hệ thống số mà trong đó một dạng tổng quát của giải thuật Euclid có thể được xác định. Những năm cuối thế kỷ 19, giải thuật Euclid dần bị lu mờ bởi lý thuyết tổng quát của Dedekind về ideal.[44]

Nhiều ứng dụng khác của giải thuật Euclid cũng đã được phát triển trong thế kỷ 19. Năm 1829, Charles Sturm cho thấy rằng giải thuật này có ích trong phương pháp chuỗi Sturm dùng để đếm số nghiệm thực của đa thức trong một khoảng bất kỳ.[45]

Giải thuật Euclid là thuật toán liên hệ số nguyên đầu tiên dùng để tìm mối liên hệ số nguyên giữa các số thực tương xứng. Nhiều thuật toán khác như vậy cũng đã được phát triển, chẳng hạn như thuật toán của Helaman Ferguson và R.W. Forcade (1979)[46] hay thuật toán LLL.[47][48]

Năm 1969, Cole và Davie đã tạo ra một trò chơi hai người dựa trên giải thuật Euclid có tên là The Game of Euclid.[49] Trò chơi này có một chiến lược chơi tối ưu.[50] Mỗi người chơi bắt đầu với hai đống đá chứa a và b viên đá, lần lượt loại bỏ m bội của đống nhỏ hơn so với đống lớn hơn. Như vậy, khi a lớn hơn b thì người tiếp theo có thể giảm số lượng viên đá trong đống lớn từ a xuống a − mb viên. Người chiến thắng là người đầu tiên có một đống không còn viên đá nào.[51][52]